package com.kuang.array;

/*
*   给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

    子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2
* */


import java.util.HashMap;

/**
 * @author kjx
 */
public class SubarraySum {
    //第一种方法还是暴力求解
    //这个有点像KMP算法，就是在字符串中找子串，但是显然我不会
    public int subarraySum(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int addNum = nums[i];  //累加和
            for (int j = i; j < nums.length; j++) {
                addNum = j == i ? addNum : addNum + nums[j];
                result = addNum == k ? result + 1 : result;
            }
        }
        return result;
    }


    //第二种方法利用前缀和，这个概念是非常常见的，但是我居然今天才知道！！！！！
    //两个前缀和相减如果=k，则能证明有一个子数组
    //因此问题转换为求所有差为k的数量了，这里没必要提前把前缀和全算出来再遍历，直接边求前缀和边计算
    //因此需要用到东西来存储，最方便的就是 HashMap了
    public int subarraySum2(int[] nums, int k) {
        //用于保存前缀和和出现的次数,key为前缀和,value为出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);   //刚好相等的情况
        int result = 0, preSum = 0;
        for (int num : nums) {
            preSum += num;
            result = map.containsKey(preSum - k) ? result + map.get(preSum - k) : result;
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return result;
    }
    //整体思路是比较复杂的，尤其是代码可读性极差，未来需要复习看视频：
    //【算法面试实录-和为 k 的子数组】https://www.bilibili.com/video/BV1gN411E7Zx?vd_source=28858aa71843116c30891e8df183b6ab


    public static void main(String[] args) {

    }
}
